The present invention relates to memory usage in a computer system and more particularly to a method and system for providing a variable aging interval for aging a memory resource.
FIG. 1 depicts a simplified block diagram of a portion of a computer system 10. The computer system includes a memory 12, a processor 14, a large capacity storage 16, an input/output mechanism 18, such as a keyboard, monitor or network, and a computation procedure for generating memories 20. The memory 12 is used to temporarily store items which may be used by the processor 14 in performing various tasks. Typically, when the processor 14 requires an item, the memory 12 is searched first. If the item is found in the memory 12, the item is provided directly to the processor 14. When an item that is searched for is not found in the memory 12, the item is typically found by searching the large capacity storage 16, or other by other means. The new item is generally provided to the memory 12 and the processor 14. Alternatively, a new memory is computed by some procedure 20, such as generation of a forwarding table. Thus, if the processor 14 requires the item again, the memory 12 may contain the item.
Items stored in the memory 12 are desired to be rapidly and easily accessible by the processor 14. Items stored in the memory 12 can be more rapidly retrieved than items stored in the large capacity storage 16. Similarly, items stored in the memory 12 can be more rapidly retrieved than items recomputed by some procedure 20, such as generation of a forwarding table. Thus, the memory 12 may be a cache. In order for the interaction between the memory 12 and the processor 14 to be efficient, the memory 12 is made relatively small. Consequently, the memory 12 is typically much smaller than the large capacity storage 16. Memory retrieval from the memory 12 is also much faster than recomputation. The small size of the memory 12 reduces unnecessary delay in retrieving items in the memory 12.
Furthermore, the full capacity of the memory 12 is not desired to be used. If the memory 12 becomes full it is difficult to store additional items. Thus, the occupancy of the memory 12 is desired to be below the maximum possible occupancy. In addition, when fewer items are stored in the memory 12, the problem of finding a location to store new items is simplified. The search of the memory 12, therefore, consumes less time. Thus, the memory 12 and processor 14 can operate more efficiently.
Furthermore, it is desirable for the hit ratio to be relatively large. The hit ratio is the ratio of the number of times a search in the memory 12 results in the desired item being found to the total number of times the memory 12 is searched. If the hit ratio is relatively high, then the memory 12 is storing those items that are repeatedly used. However, as discussed above, the occupancy of the memory 12 should still remain below the maximum occupancy in order to improve the speed of accessing to the memory 12 or adding new items to the memory 12.
One of ordinary skill in the art will readily realize that without management, the efficiency of the memory 12 may not be maintained. As discussed above, a large hit ratio, a small size, and a relatively low occupancy are generally desired for the memory 12. These are competing goals. A larger memory 12 having a higher occupancy stores more items, allowing for a larger hit ratio. However, a small memory 12 with a relatively low occupancy has a high speed. As the size of the memory 12 decreases, it becomes more important to store only those items which will be reused by the system 10 in order to preserve a higher hit ratio. Furthermore, items that the processor 14 cannot find in the memory 12 are stored in the memory 12 when the items are found, either being recalled from the large capacity memory 16 or generated by the computation procedure 20. Unchecked, the memory 12 may become full, unable to store additional items, and function improperly. Items stored in the memory 12 may also become seldom used or may never be used again. These items may unnecessarily clutter the memory 12. Thus, some mechanism for managing, or aging, the memory 12 is used to attempt to improve the efficiency of the memory 12.
There are many conventional mechanisms for aging the memory 12. One conventional mechanism keeps the memory 12 relatively full, discarding the least recently used item for additional space. Other conventional mechanisms use variations of purging the least recently used items or purging the memory 12 when the memory 12 is full or almost full. However, in such a case, the occupancy of the memory 12 is relatively high, making it difficult to store additional items. Thus, another mechanism is often used for managing the memory 12.
FIG. 2A depicts one conventional method 50 for purging the memory 12 periodically in order to age the memory 12. A purge of the memory removes some of the items of the memory 12, for example those items not sought since the previous purge and not added during the same time period, or epoch. A conventional aging period, which sets the time between purges of the memory 12, is set, via step 52. An epoch for the memory is a time equal to the conventional aging period. The time since the last purge is then set to zero, via step 54. It is determined whether the memory is near full, via step 56. If so, then the memory 12 is purged immediately, via step 58. Steps 56 and 58 allow for accelerated purging of the memory 12. Accelerated purging helps prevent the memory 12 from becoming full. Step 54 is then returned to.
If it is determined in step 56 that the memory is not nearly full, then it is determined if the current epoch is completed, via step 60. In other words, it is determined whether a time equal to the conventional aging period has expired, via step 60. If the time equal to the conventional aging period has not expired, then step 56 is returned to. If it is determined that the current epoch has expired, then the memory is purged, via step 62. Step 54 is then to returned to.
Thus, the conventional method 50 periodically removes items from the memory 12 at the end of each epoch, for example those items not referenced and not added during the just completed epoch. The conventional aging period is typically set by a user, such as a network administrator. The network administrator typically sets the conventional aging period based on the network administrator""s experience or knowledge of the computer system 10. The memory 12 is purged upon expiration of each conventional aging period.
FIG. 2B depicts a time line 70 for the conventional method 50. The conventional aging period, A, defines the lengths of the epochs 72 and 74. Each epoch 72 and 74 is followed by a purge 73 and 75, respectively. Additional epochs (not shown) and purges (not shown) follow during operation of the computer system 10 using the conventional method 50. Thus, the conventional aging period sets the time between the end of one purge and the beginning of a subsequent purge. During a purge 73 or 75, the memory 12 is typically unavailable for other operations.
Referring to FIGS. 2A and 2B, the purging steps 58 and 62 are conventionally carried out in a number of ways. Some conventional systems simply delete all of the items in the memory 12 when the memory 12 is full instead of relying on the conventional aging period. Thus, steps 58 and 62 could purge all or merely some of the items in the memory 12. In one conventional method 50, the number of items purged in step 58 and 62 is a function of the occupancy of the memory 12. When the memory 12 is nearly full, a larger number of items are deleted during the purging steps. When the memory 12 is closer to being empty, fewer items are deleted in the purging steps. In another conventional method, the items in the memory 12 are put into classes based on usage or recent addition to memory. Items are deleted based on the class.
Thus, the memory 50 periodically removes items from the memory 12. Consequently, the occupancy of the memory 12 can be lowered and the hit ratio of the memory 12 may be raised. Although the conventional method 50 functions, one of ordinary skill in the art will readily realize that the conventional method may be inefficient. During normal operation, the conventional method depends largely upon the conventional aging period set by the system administrator. Furthermore, purging the memory 12 based solely on the occupancy or on the class of the items stored in the memory may adversely affect the performance of the memory 12. Thus, the rate at which the memory 12 is purged may be higher or lower than is desirable. Purging less often than is desirable leaves more items in the memory 12 than is desired, slowing the time required to find an item that is used or complicating insertion of new items. Purging the memory 12 more often than is desired also slows the system 10 because each purge requires a certain amount of time and might prevent the memory 12 from being used during this time. In addition, deleting an item prematurely means that the item will have to be added again the next time the item is sought. Furthermore, the number of purged items may be different from what is desired. As a result, the conventional memory 12 functions in less efficient manner than is desired.
Accordingly, what is needed is a system and method for aging the memory of the computer system to account for the behavior of the memory. The present invention addresses such a need.
The present invention provides a method and system for performing aging of a memory in a computer system. The memory contains a plurality of items. The method and system comprise purging the memory of a portion of the plurality of items each time an epoch equal to an aging variable has expired. The method and system further comprise providing the aging variable for a new epoch based on a performance of the memory in a previous epoch, including the aging variable of the previous epoch.
According to the system and method disclosed herein, the present invention provides a mechanism for updating the aging the memory of a computer system based on the performance of the computer system.